# 8, 4, 2, 1
# 32, 16, 8, 4, 2, 1
class Solution:
    def __init__(self):
        self.hour = {}
        self.minute = {}

    def readBinaryWatch(self, num: int) -> list:
        res = []
        for i in range(max(0, num - 5), min(num, 3)+1):
            hour = self.search_hour(i)
            minute = self.search_minute(num - i)
            res.extend(i + ":" + j for i in hour for j in minute)
        return res

    def search_hour(self, n):
        if n in self.hour:
            return self.hour[n]
        else:
            mid_res = []
            for i in range(12):
                if bin(i).count("1") == n:
                    mid_res.append(str(i))
            self.hour[n] = mid_res
            return mid_res

    def search_minute(self, n):
        if n in self.minute:
            return self.minute[n]
        else:
            mid_res = []
            for i in range(60):
                if bin(i).count("1") == n:
                    mid_res.append(str(i).rjust(2, "0"))
            self.minute[n] = mid_res
            return mid_res


a = Solution()
print(a.readBinaryWatch(0))
print(a.readBinaryWatch(1))
print(a.readBinaryWatch(2))
